 template <typename TYPENAME> static void advance_sort( TYPENAME * const a, size_t size );
 template <typename TYPENAME> inline void advance_partial_sort( TYPENAME * const a, size_t r, size_t g, size_t end );
 
 #include <vector>
 
 // a = array of elements to be sorted
 // size = number of elements in the array
 // g = comparison group index
 // r = radius of comparison
 // (e.g. if we compare (1 2) | (3 4), then r = 4)
 template <typename TYPENAME>
 static void advance_sort( TYPENAME * const a, size_t size )
 {
    for ( size_t r = 0x2; (r / 0x2) < size; r *= 0x2 )
    {
        for ( size_t g = 0x0; g < size; g += r )
        {
	        if ( r <= size - g )    // if the group to sort is equal to the radius
	        {
		       advance_partial_sort( a, r, g, r + g );
	        }
	        else	// r > size - g
		            // same as above, except 
		            // 1) "j < r + g" is changed to "j < size"
	        {
		        // Example for r = 4:
		        //
		        // (1 2 | 3) <-- not sorted
		        // (1 2 | 3 4) | (5)	<-- already sorted
		        // (1 2 | 3 4) | (5 7)	<-- already sorted
		        // (1 2 | 3 4) | (5 7 | 6)  <-- not sorted

		        if ( r/2 < size - g )	// if r/2 >= size - g, then this group is already sorted, so do not sort
		        {
                    advance_partial_sort( a, r, g, size );
		        }
	        }
	        
	        #ifdef PRINT_ADVANCE_SORT
	        printf("    While Sorting g = %1d\n", g);
            printf("    Array: ");
            for ( int i = 0x0; i < size; ++i )
            {
                printf("%1d ", a[i]);
            }
            printf("\n");
            #endif
        }
        
        #ifdef PRINT_ADVANCE_SORT
        printf("While Sorting r = %1d\n", r);
        printf("Array: ");
        for ( int i = 0x0; i < size; ++i )
        {
            printf("%1d ", a[i]);
        }
        printf("\n");
        #endif
    }
 }
 
 // g = begin
 template <typename TYPENAME>
 inline void advance_partial_sort( TYPENAME * const a, size_t r, size_t g, size_t end )
 {
    size_t split = (r / 0x2) + g;  // the split point is at the half way point of the group
    size_t mod = 0x0;
    std::vector<size_t> v;
    for ( size_t i = split - 1; i >= g; --i )
    {
        bool hasSwap = false;
        TYPENAME* x = &a[i];
        for ( size_t j = end - 1 - mod; j >= split; --j )
        {
	        TYPENAME* y = &a[j];
	        if ( *x > *y ) //!compare( *x, *y ) )
	        {
		        std::swap( *x, *y );
		        x = y; // move pointer
		        
		        v.push_back( j );
		        
		        // Example reason for ++mod:
		        // 1 5 6   4  |  2 3 7 9
		        //     x+1 y         x	<-- pointers
		        //
		        // We know 6 < 7, so the next pointer at x+1 (i.e. content 6), should only compare with
		        // the indexes before the location of content 7 (e.g. in this case, content 3).
		        //
		        // Result:
		        // 1 5 6 4  |  2 3 7 9
		        //     x		 y x-1	<-- pointers
		        ++mod; // if swap, then next number do numberOfComparison - 1 (i.e. 1 less comparison)
		        hasSwap = true; // Unnecessary?
		        
		        // swap has occurred, so we do not need to do any further checking
		        // Thus, break out of for-loop
		        break;
	        }
		    
		    /*printf("            While Sorting j = %1d\n", j);
            printf("            Array: ");
            for ( int i = 0x0; i < end; ++i )
            {
                printf("%1d ", a[i]);
            }
            printf("\n");*/
        }
        
        // if no swap has taken place, no more swaps will take place
        if ( !hasSwap )
        {
            break;
        }
        
        #ifdef PRINT_ADVANCE_SORT
        printf("        While Sorting i = %1d\n", i);
        printf("        Array: ");
        for ( int i = 0x0; i < end; ++i )
        {
            printf("%1d ", a[i]);
        }
        printf("\n");
        #endif
    }
    
    size_t m = 0x0;
    for ( size_t k = 0; k < v.size(); ++k )
    {
        size_t j = v[k] - 1;
        size_t i = split - 1 - m;//(end - j - 1);
        j -= m;
        
        // range of current swap compared to next swap
        size_t range = ( k + 1 < v.size() ? v[k] - v[k+1] /*- 0x1*/ : 0x2 );
        
        TYPENAME* x = &a[i];
        TYPENAME* y = &a[j];
        
        #ifdef PRINT_ADVANCE_SORT
        printf("            While Sorting k = %1d\n", k);
        printf("            v[k]: %1d split: %2d end: %3d\n", v[k], split, end);
        printf("            i: %1d j: %2d\n", i, j);
        printf("            a[i]: %1d a[j]: %2d\n", a[i], a[j]);
        printf("            Array: ");
        for ( int i = 0x0; i < end; ++i )
        {
            printf("%1d ", a[i]);
        }
        printf("\n");
        #endif
        
        // if range is greater than 1, then certainly *x > *y 
        if ( range > 0x1 )
        {
            // Example reason for the swap:
            // (1 3 5 7) | (2 4 6 8)
            //        x     i+1 j
            //
            // Result:
            // (1 3 5 2) | (4 6 7 8)
            //                  x 
            #ifdef PRINT_ADVANCE_SORT
            printf("            Before Swap *y: %1d\n", *y);
            TYPENAME temp = *x;
            memcpy( x, &a[i+1], (j - i)*sizeof(TYPENAME) );
            *y = temp;
            printf("            After Swap *y: %1d\n", *y);
            #endif
            
            ++m; // notice in the above example, content 4 has moved 1 index back;
        }
        else 
        {
            bool hasSwap = false;
            // Example reason for for-loop:
            // (1 3 5 5) | (2 6 7 8)
            //        i         j
            //
            // Result:
            // (1 3 5 2) | (5 6 7 8)
            //              x     
            for ( size_t n = j; n > i; --n )
            {
                y = &a[n];
                if ( *x > *y ) // !compare( *x, *y )
                {
                    TYPENAME temp = *x;
                    memcpy( x, &a[i+1], (n - i)*sizeof(TYPENAME) );
                    *y = temp;
                    hasSwap = true;
                    
                    ++m;
                    break; // if swap has occurred, break out of for-loop
                }
            }
            
            // No more swap will occur, period, if no swap occurs here
            if ( !hasSwap )
            {
                // bubble-up
                // &a[i - (v.size() - k)]
                // std::vector<TYPENAME> temp( x + 1 - (v.size() - k), x + 1 );
                /*
                size_t mod_2 = 0x0;
                for ( size_t s = i - (v.size() - k - 1); s <= i; ++s )
                {
                    y = &a[s];
                    for ( size_t t = s - 1; t >= ( mod_2 != 0x0 ? mod_2 : g ); --t )
                    {
                        x = &a[t];
                        
                        if ( *x > *y ) // !compare(*x, *y)
                        {
                            //x = &a[--t];
                            
                            while ( a[--t] > *y ); // !compare(*x, *y) 
                            {
                                if ( t < ( mod_2 != 0x0 ? mod_2 : g ) )
                                    break;
                                    
                                x = &a[t];
                            }
                            
                            ++t;
                            //x = &a[t + 1];
                            
                            TYPENAME temp = *y;
                            memcpy( &a[t+1], x, sizeof(TYPENAME)*(s - t) );
                            *x = temp;
                            
                            mod_2 = t + 1;
                            break;
                        }
                        else
                        {
                            return;
                        }
                    }
                }*/ 
            
                break;
            }
        }
        
    }
 }